/// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
pub struct Solution;

impl Solution {
    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.3 MB , 在所有 Rust 提交中击败了 50.88% 的用户
    /// 这个例子有很好的性质：有序，这里没有利用有序的性质
    /// 时间复杂度：O(2n)
    pub fn search_range_iter(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut iter = nums.iter().enumerate();
        let a = iter.find(|&(_, x)| *x == target).map(|(i, _)| i as i32).unwrap_or(-1);
        let b = if a < 0 {
            -1
        } else {
            iter.skip_while(|&(_, x)| *x == target)
                .map(|(i, _)| i as i32 - 1)
                .next()
                .unwrap_or(nums.len() as i32 - 1) // or 的情况：迭代器已结束
        };
        vec![a, b]
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.2 MB , 在所有 Rust 提交中击败了 81.97% 的用户
    /// 时间复杂度：O(2*log n)；优解
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let n = nums.len();
        if n == 0 || target < nums[0] || target > nums[n - 1] {
            vec![-1, -1] // 超出范围
        } else {
            // println!("\n{} target {}", "-".repeat(20), target);
            let a = Solution::search(&nums, target, 0, true);
            vec![a, Solution::search(&nums, target, a, false)]
        }
    }

    const fn search(nums: &[i32], target: i32, i: i32, lower: bool) -> i32 {
        if i < 0 {
            return i; // 第一次未找到，直接返回 -1
        }
        let (mut i, mut j, n) = (i as usize, nums.len() - 1, nums.len());
        let mut mid: usize;
        while i <= j {
            mid = (i + j) / 2;
            // vec_pos!(nums; i=i,k=mid,j=j);
            if target > nums[mid] || (!lower && mid < n - 1 && nums[mid + 1] == target) {
                i = mid + 1; // 正常的二分法 || 解决中点落在重复序列内
            } else if target < nums[mid] || (lower && mid > 0 && nums[mid - 1] == target) {
                j = mid - 1; // 正常的二分法 || 解决中点落在重复序列内
            } else {
                return mid as i32;
            }
        }
        -1 // target 不在这个序列时，返回 -1
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.3 MB , 在所有 Rust 提交中击败了 68.52% 的用户
    /// 时间复杂度不合格：最差情况可能出现 O(n)
    pub fn search_range_dichotomy_awful(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let n = nums.len();
        if n == 0 || target < nums[0] || target > nums[n - 1] {
            vec![-1, -1] // 超出范围
        } else {
            let (mut i, mut mid, mut j) = (0, n / 2, n - 1);
            // println!("\ntarget {}", target);
            while i <= j {
                // vec_pos!(nums; i=i,k=mid,j=j);
                if target < nums[mid] {
                    j = mid - 1;
                } else if target > nums[mid] {
                    i = mid + 1;
                } else {
                    let (mut l, mut r) = (mid, mid); // 解决中点落在重复序列内
                    while l > 0 && nums[l - 1] == target {
                        l -= 1;
                    }
                    while r < n - 1 && nums[r + 1] == target {
                        r += 1;
                    }
                    return vec![l as i32, r as i32];
                }
                mid = (i + j) / 2;
            }
            vec![-1, -1] // target 不在这个序列时，返回 -1
        }
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.4 MB , 在所有 Rust 提交中击败了 11.11% 的用户
    /// 时间复杂度不合格：最差情况可能出现 O(n) ，与 search_range_dichotomy_awful 差不多
    /// https://rustgym.com/leetcode/34
    pub fn search_range_gym(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let n = nums.len();
        match nums.binary_search(&target) {
            Ok(x) => {
                let (mut i, mut j) = (x, x);
                while i > 0 && nums[i - 1] == target {
                    i -= 1;
                }
                while j + 1 < n && nums[j + 1] == target {
                    j += 1;
                }
                vec![i as i32, j as i32]
            }
            Err(_) => vec![-1, -1],
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, i32) -> Vec<i32> {
        assert_eq!(f(vec![5, 7, 7, 8, 8, 10], 5), vec![0, 0]);
        assert_eq!(f(vec![5, 7, 7, 8, 8, 10], 7), vec![1, 2]);
        assert_eq!(f(vec![5, 7, 7, 8, 8, 10], 8), vec![3, 4]);
        assert_eq!(f(vec![5, 7, 7, 8, 8, 10], 6), vec![-1, -1]);
        assert_eq!(f(vec![], 0), vec![-1, -1]);
        assert_eq!(f(vec![1], 0), vec![-1, -1]);
        assert_eq!(f(vec![1], 1), vec![0, 0]);
        assert_eq!(f(vec![1, 4], 4), vec![1, 1]);
        assert_eq!(f(vec![1, 2, 2], 1), vec![0, 0]);
        assert_eq!(f(vec![1, 4, 4], 4), vec![1, 2]);
        assert_eq!(f(vec![3, 3, 3], 3), vec![0, 2]);
        assert_eq!(f(vec![1, 2, 3, 3, 3, 3, 4, 5, 9], 3), vec![2, 5]);
        assert_eq!(f(vec![1, 2, 2, 3, 4, 4, 4], 4), vec![4, 6]);
        assert_eq!(f(vec![1, 2, 2, 3, 4, 7, 7], 4), vec![4, 4]);
        assert_eq!(f(vec![1, 2, 2, 3, 4, 7, 7], 5), vec![-1, -1]);
        assert_eq!(f(vec![1, 2, 2, 3, 4, 7, 7], 7), vec![5, 6]);
    }

    bench!(assert Solution::search_range_iter);
    bench!(assert Solution::search_range);
    bench!(assert Solution::search_range_dichotomy_awful);
    bench!(assert Solution::search_range_gym);
}
